package chapter02;

public class TotalNQueens52 {
    /**
     * 回溯+位运算
     * 递归含义：当前行皇后放置后满足下一行皇后条件的可能结果
     * 1.limit==(1<<n)-1 二进制从右到左1~n位全为1 其余为0
     * 2.colLim leftLim rightLim
     *   列限制  左上对角线限制  右上对角线限制
     *   都是二进制表示 从右到左共n位 0可以放 1不可以放
     * 3.pos=limit&(~(colLim|leftLim|rightLim))  表示成二进制位上有1就可以放
     * 4.mostRightOne=pos&(-pos) 取出最右侧1
     *   pos=pos-mostRightOne 最右侧1上考虑过 变为0
     * 5.colLim|mostRightOne  把新增皇后位置加入列限制
     *   (leftLim|mostRightOne)<<1 更新左上对角线限制
     *   (rightLim|mostRightOne)>>>1 更新右上对角线限制
     * 递归出口：
     *     当colLim==limit 表明列限制已满
     *     return 1 返回一种可能性
     */
    //位运算
    public int totalNQueens(int n) {
        return process((1<<n)-1,0,0,0);
    }

    public int process(int limit,int colLim,int leftLim,int rightLim) {
        if(colLim==limit){
            return 1;
        }
        int res=0;
        int pos=limit&(~(colLim|leftLim|rightLim));
        while (pos!=0){
            int mostRightOne=pos&(-pos);
            pos-=mostRightOne;
            res+=process(limit,colLim|mostRightOne,(leftLim|mostRightOne)<<1,(rightLim|mostRightOne)>>>1);
        }
        return res;
    }

    //数组记录
    int[] record;
    public int totalNQueens1(int n) {
        record=new int[n];
        return process1(n,0);
    }

    public int process1(int n,int pos) {
        if(pos==n){
            return 1;
        }
        int res=0;
        for(int i=0;i<n;i++){
            if(isValid(pos,i)){
                record[pos]=i;
                res+=process1(n,pos+1);
            }
        }
        return res;
    }

    public boolean isValid(int pos,int col){
        for(int i=0;i<pos;i++){
            if(col==record[i]||Math.abs(i-pos)==Math.abs(record[i]-col)){
                return false;
            }
        }
        return true;
    }

}
